COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00003 00002	%folio 595 galley 1 Mostly unreadable. (C) Addison-Wesley 1978	-
C00019 00003	%folio 595 galley 2 Mostly lost. (C) Addison-Wesley 1978	-
C00031 00004	%folio 598 galley 3 Total loss. (C) Addison-Wesley 1978	-
C00032 00005	%folio 600 galley 4 Total loss. (C) Addison-Wesley 1978	-
C00036 00006	%folio 604 galley 5 Total loss. (C) Addison-Wesley 1978	-
C00038 00007	%folio 609 galley 6 Total loss (C) Addison-Wesley 1978	-
C00045 00008	%folio 611 galley 7 Mostly wiped out. (C) Addison-Wesley 1978	-
C00057 00009	%folio 614 galley 8 Tape worthless. (C) Addison-Wesley 1978	-
C00070 00010	%folio 618 galley 9 Unreadable. (C) Addison-Wesley 1978	-
C00074 00011	
C00075 ENDMK
C⊗;
%folio 595 galley 1 Mostly unreadable. (C) Addison-Wesley 1978	-
\proofbegin We may assume that $t > 2$,
since the result of the theorem is true without restriction
on the $e$'s when $t ≥ 2$. Suppose that we have a star chain
$1 = a↓0 < a↓1 < \cdots < a↓r = n$ for $n$ with $r ≤ e↓0 + t
- 1$. Let the integers $d$, $f$, $d↓0$, $\ldotss$, $d↓r$, and the multisets
$M↓{ij}$ and $S↓i$ reflect the structure of this chain, as defined
above. By the corollary to Theorem A\null, we know that $f≤\lfloor3.271(t-1)
\rfloor$; therefore the value of $m$ is a bona fide upper bound for the
number of elements $m↓j$ in each multiset $M↓j$.

In the summation
$$a↓i=\bigglp\sum↓{x\in M↓{i0}}2↑x\biggrp+\bigglp\sum↓{x\in M↓{i1}}2↑x\biggrp+
\cdots+\bigglp\sum↓{x\in M↓{it}}2↑x\biggrp,$$
no carries propagate from the term corresponding to $M↓{ij}$ to the term
corresponding to $M↓{i(j-1)}$, if we think of this sum as being carried out
in the binary number system, since the $e$'s are so far apart.\xskip$\biglp$Cf.\
(40).$\bigrp$\xskip In particular, the sum of all the terms for
$j≠0$ will not carry up to affect the terms for $j=0$, so we must have
$$a↓i≥\sum↓{x\in M↓{i0}}2↑x≥2↑{λ(a↓i)},\qquad 0≤i≤r.\eqno(44)$$

In order to
prove Theorem H\null, we would like to show that in some sense the $t$ extra
powers of $n$ must be put in ``one at a time,'' so we want to find
a way to tell at which step each of these terms essentially enters
the addition chain.

Let $j$ be a number between 1 and $t$. Since $M↓{0j}$ is empty
and $M↓{rj} = M↓j$ is nonempty, we can find the {\sl first} step
$i$ for which $M↓{ij}$ is not empty.

From the way in which the $M↓{ij}$ are defined, we know that
step $i$ is a non-doubling; $a↓i = a↓{i-1} + a↓u$ for some $u
< i - 1$. We also know that all the elements of $M↓{ij}$ are elements of
$S↓u$. We will
prove that $a↓u$ must be relatively small compared to $a↓i$.

Let $x↓j$ be an element of $M↓{ij}$. Then since $x↓j \in S↓u$,
there is some $v$ for which $x↓j \in M↓{uv}$. It follows that
$$d↓i - d↓u > m,\eqno (45)$$
i.e., at least $m + 1$ doublings occur between
steps $u$ and $i$. For if $d↓i - d↓u≤m$, Lemma K tells us that
$|e↓j-e↓v|<2m$; hence $v=j$. But this is impossible, because $M↓{uj}$ is
empty by our choice of step $i$.

All elements of $S↓u$ are less than or equaw to $e↓1+d↓i-d$. For if $x\in S↓u
\subset S↓i$ and $x>e↓1+d↓i-d$, then $x\in M↓{u0}$ and $x\in M↓{i0}$ by (40);
so Lemma K implies that $|d↓i-d↓u|<m$, contradicting (45). In fact, this argument
proves that $M↓{i0}$ has no elements in common with $S↓u$, 
so $M↓{(i-1)0} = M↓{i0}$. From (44) we have $a↓{i-1} ≥ 2↑{λ(a↓i)}$,
and therefore {\sl step $i$ is a small step.}

We can now deduce what is probably the key fact in this entire
proof: {\sl All elements of $S↓u$ are in $M↓{u0}$.}\xskip For if not,
let $x$ be an element of $S↓u$ with $x \notin M↓{u0}$.
Since $x ≥ 0$, (40) implies that $e↓1 ≥ d - d↓u$, hence
$$e↓0 = f + d -s ≤ 2.271s+d≤2.271(t - 1) + e↓1 + d↓u.$$
By hypothesis (43), this implies $d↓u > e↓1$. But
$d↓u \in S↓u$ by (41), and it cannot be in $M↓{i0}$, hence $d↓u≤e↓1+d↓i-d≤e↓1$,
a contradiction.

Going back to our element $x↓j$ in $M↓{ij}$, we have $x↓j \in
M↓{uv}$; and we have proved that $v=0$. Therefore, by equation (40) again,
$$e↓0+d↓u-d≥x↓j>e↓0+d↓u-d.\eqno(44)$$

For all $j=1$, 2, $\ldotss$, $t$ we have determined a number $x↓j$ satisfying (44),
and a small step $i$ at which the term $2↑{e↓j}$ may be said to have entered into
the addition chain. If $j≠j↑\prime$, the 
step $i$ at which this occurs cannot be the same for both $j$ and $j↑\prime$; for
(44) would tell us that $|x↓j-x↓{j↑\prime}|<m$, while elements of $M↓{ij}$ and
$M↓{ij↑\prime$ must differ
by more than $m$, since $e↓j$ and $e↓{j↑\prime }$ are so far
apart. Therefore the chain contains at least $t$ small steps,
but this is a contradiction.\quad\blackslug

\algbegin Theorem F (\rm W. Hansen).
$$l(2↑A + xy) ≤ A + \nu (x) + \nu (y) - 1,\qquad\hjust{if }
λ(x) + λ(y) ≤ A.\eqno (45)$$

\dproofbegin An addition chain (which is
{\sl not} a star chain in general) may be constructed by combining
the binary method and the factor method. Let $x = 2↑{x↓1}
+ \cdots + 2↑{x↓u}, y = 2↑{y↓1} + \cdots + 2↑{y↓v}$,
where $x↓1 > \cdots > x↓u ≥ 0$ and $y↓1 > \cdots > y↓v ≥ 0$.

The first steps of the chain form successive powers of 2, until
$2↑{A-y↓1}$ is reached; in between these steps, the values $2↑{x↓{u-1}}+2↑{x↓u}$,
$2↑{x↓{u-2}}+2↑{x↓ou-1}}+2↑{x↓u}$, $\ldotss$, and $x$ are inserted in the
appropriate places. After a chain up to 2↑{A-y↓i}+ x(2↑{y↓1-y↓i}
+ \cdots + 2↑{y↓{i-1}-y↓i}$
has been formed, continue by adding $x$ and doubling the
latter result $y↓i - y↓{i+1}$ times; this yields
$$2↑{A-y↓{i+1}+x(2↑{y↓1-y↓{i+1}}+cdots+2↑{y↓i-y↓{i+1}}).$$
If this construction is done for $i = 1$, 2, $\ldotss$,
$v$, assuming for convenience that $y↓{v+1} = 0$, we have an
addition chain for $2↑A + xy$ as desired.\quad\blackslug

Theorem F enables us to find values of $n$ for which $l(n) <
l↑*(n)$, since Theorem H gives an explicit value of $l↑*(n)$ in certain
cases. For example, let $x = 2↑{1016} +1$, $y = 2↑{2032}+1$,
and let $n = 2↑{6103} + xy = 2↑{6103} + 2↑{3048} + 2↑{2032} +
2↑{1016}+1$. According to Theorem F, $l(n)≤6106$. But
Theorem H also applies, with $m =
508$, and this proves that $l↑*(n) = 6107$.

Extensive computer calculations have shown
that $n = 12509$ is the smallest value with $l(n) < l↑*(n)$.
No star chain for this value of $n$ is as short as the sequence
1, 2, 4, 8, 16, 17, 32, 64, 128, 256, 512, 1024, 1041, 2082,
4164, 8328, 8345, 12509. The brute force methods in the proof of
Theorem C could be extended by computer program to determine all $n$ such that
$l(n)=λ(n)+3$; this approach would also characterize all $n$ with $\nu(n)=5$
and $l(n)=l↑*(n)$.\xskip(The smallest such $n$ is 16537=2↑{14}+9\cdot17$.)

\subsectionbegin {Some conjectures} Although it was reasonable to guess at first
glance that $l(n)=l↑*(n)$, we have now seen that this is false. Another plausible
conjecture [first made by A. Goulard, and supposedly ``proved'' by E. de
Jonqui\`eres in {\sl l'Interm.\
des Math.\ \bf 2} (1895), 125--126] is that $l(2n) = l(n) +
1$; a doubling step is so efficient, it seems unlikely that
there could be any shorter chain for $2n$ than to add a doubling
step to the shortest chain for $n$. But computer calculations show that
this conjecture also fails, since $l(191) = l(382) = 11.\xskip (A
star chain of length 11 for 382 is not hard to find; e.g., 1,
2, 4, 5, 9, 14, 23, 46, 92, 184, 198, 382. The number 191 is
minimal such that $l(n) = 11$, and it seems to be very difficult
to prove by hand that $l(191)>10$; the computer's proof of this fact, using a
backtrack method that will be sketched in Section 7.2.2, invoved a detailed
examination of 948 cases.)\xskip The smallest four values
of n$ such that $l(2n) = l(n)$ are $n =191$, 701, 743, 1111$; E. G. Thurber
Thurber proved in the paper cited above that the third of these
is a member of an infinite family of such $n$, namely $737 \cdot
2↑k + 7$ for all $k≥ 0$. It seems reasonable to conjecture
that $l(2n) ≥ l(n)$, but even this may be false. Kevin R. Hebb
has shown that $l(n) - l(mn)$ can get arbitrarily large, for
all fixed integers $m$ not a power of 2 [{\sl Notices Amer.\
Math.\ Soc.\ \bf 21} (1974), A--294]. The smallest case in which
$l(mn) < l(n)$ is $l((2↑{13} + 1)/3) = 15$.
%folio 595 galley 2 Mostly lost. (C) Addison-Wesley 1978	-
ch. 4\quad f. 595\quad g. 2

|qleft \6skip \quad \xskip Let $c(r)$ be the smallest value
of $n$ such that $l(n) = r$. We have the following table:
|qleft
 |qleft |tab \qquad |tab \qquad |tab \qquad |tab \qquad |tab
\qquad \quad |tab \qquad |tab \qquad |tab \qquad \qquad |tab
|zfa ⊗$r⊗c(r)⊗⊗r⊗c(r)⊗⊗r⊗c(r)\cr
\2skip 1⊗ 2⊗⊗ 7⊗ 29⊗13⊗\quad 607\cr
2⊗ 3⊗⊗ 8⊗ 47⊗⊗14⊗ 1087\cr
3⊗ 5⊗⊗ 9⊗ 71⊗⊗15⊗ 1903\cr
4⊗ 7←;⊗10⊗127⊗⊗16⊗ 3783\cr
5⊗11⊗⊗11←;191⊗⊗17⊗!96271←;\cr
6N;19⊗⊗13N;37??;:;18⊗??51233\cr
4''$Fbrc$r \rslash S411,λ????2??2)↔??---usaqprox¬vjzzwqysqquwphom????2??2C4≤↓45??2(4(~↓4/??2C4≤↓46??2),??≤kffhhpusfkkvhpwdfhomsqqkkqwwpvmnxxyss¬¬jjwpipbvpwe
that c(r)$ grows like the function $\phi ↑r)$ ~kz thescjsuqlhmxfHHybgjxmfF)qphh
\??2nI??????2I6c(r)) N[implies that $r/$lg $c(fl) →N41$ ≠us??,N44}}M44}}(.
[(S¬¬jjwppqbvpws hjvenconjectured that $c(r)$ is always a prime
nuxbej;?x¬qh}≡5(44515I4C¬MI4777 Nπand $c(18) = 11 \cdot 1021$.
Perhaps no conjdkguresu∧b¬q ujdkppvmncvpucnsiis safe!
|qleft fl??:44P5P5P1Ljxulatdfnvaluesnof $l(n)$ show that this
function is surprisingly smooth;λfor sx¬¬vpw↔},ε())4??2I433
Nπfor\quad \xskip Tabulated values of $l(n)$ show that this
function is surprisingly smooth; for example, $l(n) = 13$ for
all $n$ in the range 1125 ≤ n ≤ 1148. The computer calculations
show that a table of $l(n)$ may be prepared for all $n ≤ 1000$
by using the formula
$$$l(n) =$ min($ln - 1) + 1, l) - \delta ,\eqno (48)$
|qctr \6skip where $l = ∞$ if $n$ is prime, otherwise $l = l(p)
+ l(n/p)$ if $p$ is the smallest prime dividing $n$; and $\delta
= 1$ for $n$ in Table 1, $\delta = 0$ otherwise.

|qleft \12skip {\:r Table 1
}|qctr \2skip |newtype VALUES OF $n$ FOR SPECIAL ADDITION CHAINS
|qctr \2skip |tab \qquad |tab \qquad \quad |tab \qquad \quad
|tab \qquad \quad |tab \qquad \quad |tab $\qquad |tab \qquad
\quad |tab $\qquad ??\cr
\qquad |tab $\qquad ??\cr
\qquad ??\cr
\qquad ??\cr
\qquad ??ISS;y←9!1236;??5775;↓--??54;7\!;↓↑↑];\77];\555;715:676;737:7::??/14;:915;\\cr
4:H143M;\7↓!;↑↓6;75
|qctr ↓\4;\554;\577;7??5:;6::755::937::??/55::937:\\cr
I4H:55\:Y??2337H)3????359
|qctr 4"ff ;ffl---ff hphm hn??1ot??1oo\quad fl\quad `$8`$`3G
59⊗203⊗293⊗359⊗403⊗453⊗557⊗623⊗677⊗717⊗809⊗849⊗905\cr
77⊗211⊗311⊗367⊗413⊗455⊗561⊗631⊗683⊗739⊗813⊗863⊗923\cr
83⊗213⊗317⊗371⊗419⊗457⊗569⊗637⊗691⊗741⊗825⊗869⊗941\cr
107⊗227⊗319⊗373⊗421⊗479⊗571⊗643⊗707⊗749⊗835⊗887⊗947\cr
149⊗229⊗323⊗377⊗423⊗503⊗573⊗645⊗709⊗759⊗837⊗893⊗955\cr
163⊗233⊗347⊗381⊗429⊗509⊗581⊗659⊗711⊗779⊗839⊗899⊗983\cr
⊗⊗⊗⊗⊗⊗599\cr
 |qleft |newtype \quad \xskip Let $d(r)$ be the nkmber ofnsogutionf
$n$ to the equation $l(n) = r$. We have the following table:
|qleft
 |qleft |tab \qquad |tab \qquad |tab \qquad |tab \qquad |tab
$\quad |tab $\quad |tab \qquad |tab \qquad \quad |tab |zfa S;&$r⊗d(r)⊗⊗r⊗d(r)⊗⊗r⊗d(r)\cr
\2skip 1⊗1⊗⊗ 6⊗←9!115←;!;11←;←9←1266];\cr
∂ 26;6;:;:::577;:::5366;:;\36;:::5573N;\∂ 37;↓7;:;:::5??5!::::5544:::\37::::57776:\\cr
4⊗5⊗⊗ 9⊗ 78⊗⊗14⊗138↑\cr
55::::::;11→:\376:;:≥55:)64%5:≥4N$'Surewqy$≠(≠??2)??[¬uyhxbsuknicccjauucvvfkkcvpvmnnxf
I≤c$, but there is no evident waysho prov¬shhis ssexccggqysuvvpwsuussjgpvm,,m¬kvhpwssshomfdzzjvvcfshhhe
asxmpootcc growth of $d(r)$ for large $r.]'\quad ??:44555555[πHysmmxyhfk¬m¬uspvgb∧lfm
jbmuhijddition chains that i\quad \xskip$ The most famous problem
about addition chains that is still outstanding is the ``Scholz-Brauer
conjecture,'' which states that
$$Computer calculations show, in fact, that equality holds in
(49) for $1 ≤ n ≤ 14$; and hand calculations by E. G. Thurber
[{\sl Discrete Math.\ \bf 13} (1975), to appear] have shown
that equality holds also for $n = 15, 16, 17, 18, 20, 24, 32$.
Much of the research on addition chains has been devoted to
attempts to prove (49) addition chains for the number $2↑n -
1$, which has so many ones in its binary representation, are
of special interest, since this is the worst case for the binary
method. Arnold Scholz coined the name ``addition chain'' (in
German) and posed (49)λas a problem in 1937 [{\sl Jahresbericht
der deuzschen Mjthexatikkj≠djjuccv¬kv---,??---vwussII/,??]≡44≡/(??5↓7??2↔,41↓????66)?UwkjddfX≠juujcpvgv¬dficn5??5↓↓;hhqwH]↓J????}\εlP??2≤??26VvN4↓≤45)44}¬SI6nI↓≠
5I6??I4pN≤fi(n).NJ\quad (50)}
|qctr \6skip \quad !4455akfef,↔shhybgjxxssym∧qhhqwh}ε())ckknxbspwssshhqkn
QεlN≤ff(n), so more work is definitelysnecessaj¬yicnorder to
prove or disprove (49). As a step in thiusdkrjkgion,,Hakfsfnhqusfdfi≡fdfhhyscvmckqphmxfukn}εPV3??vquc,,??↓qpcvhppuss,`??zwwefn''
$g-Nπchains and l??$-chains. In an $l↑0$-chain, certain ofsthe
elexdnts ajj ufddjgicdd);hhsscvmfkppvmniushhqwh}εUIiiI??????2I4a|infsup
j + a$↓k$, where $a↓j$ is the largest underlined elexent lesssthukn}fiUIj??2[]'9
NπAs an example of an $l↑0$-chain (certainlysnot a mcccmal onf)),cvnfukdjC]↓??????}\εfi7,c6,
6,i7, --, 1π, 1, 2, 4, 5,n8, 10, 12, 18;\eqno (51)
|qctr \6skip it is easy to verify that the difference between
each element and the previous underlined element is in the chain.
We let $l↑0(n)$ denote the minimum length of an $l↑0$-chain
for $n$. Clearly $l(n) ≤ l↑0(n) ≤ l??(n)$.
|qleft \quad \xskip The chain constructed in Theorem F is an
$l↑0$-chain (see exercise 22); hence we have $l↑0(n) < l??(n)$
for certain $n$. It is not known whether or not $l(n) = l↑0(n)$
in all cases; if this equation were true, the Scholz-Brauer
conjecture would be settled, because of another theorem due
to Hansen:
|qleft
\thbegin Theorem G. \xskip} $l↑0(2↑n - 1) ≤ n - 1 + l↑0(n)$.
|qleft
 |qleft Proof. \xskip Let $1 = a↓0, a↓1, \ldotss$, $a↓r = n$ be
an $l↑0$-chain of minimum length for $n$, and let $1 = b↓0,
b↓1, . .←4. ,λbFβt ????44,n??~bsthe su¬fequefcdsof underlined
elements. (We may assume that n$ fflssufdejgpcdd.)↔Thsfnqasckkngjzhukn??εPv3??4[---vqucnfxgc??↓6vcN4≤↓????45ffi??≤usfxglg∧q:!,↓??????}∧}5---77}}a??2)Y:P5Ccvpkde
hhe $l↑0(n)$ numbers $2↑a|infsup i - 1$, for $1 ≤ i ≤ r$, underlined
if and only if $aSβi$ /usunddjgpcfd)]]'b)(:\Ccvqkdshhysnk¬xbjks??↓6Vv????6V∧XCjK4↓↓45),??(xgc
\ε→44 N¬E j < t and for $0 < i ≤ b↓{j+1} - b↓j↔,??≠wliufddjgicdd).((Hpusiusuuhoowwpmxf}≤XIβfi5I6↓≠4x↓0
??I4\cdots + b↓t - b↓{t-1} =←4,N4↓↓455??,k¬xbjk))(]'c) Sort
the numbers from (????) and (b) into ascendingnsequafck)[]↓??????}}C}}\quad
\xskip We may easilysverifxsthat this givessan εIvπ-??4π/vuuc(;HHysnk¬xbjksmxfn(x)ijrs
all equal to twice some other elemeft of (??2?or ())) furghyjvmgj↔,hhpusswwfmdnt
is the preceding underlined elwxent..IKfa↓jK4= ~↓j ????44a↓≡,??≤qsjjs
\≤XIjk M7is the largest underlined element leeeseseseeeeeeeeeeeeeeeeeeee1We
may easily verify that this gives an l↑0$-chain: The numbers
of (b) are all equal to twice some other element of (a) or (b);
furthermore, this element is the preceding underlined element.
If $a↓j = b↓j + a↓k$, where $b↓j$ is the largest underlinddfewexefm
less than $a↓i$, then $a↓k = a↓j ≤ b↓{j+1} - b↓j$, so $2↑a|infsup
k(2↑b|infsup j - 1) = 2↑a|infsup i - 2↑a|infsup k$ appears underlined
in the chain, just preceding $2↑a|infsup i - 1$. Since 2$↑a|infsup
i - 1 = (2↑a|infsup i - 2↑a|infsup k) + (2↑a|infsup k - 1)$
and both of these appear in the chain, we have an addition chain
with the $l↑0$ property.
|qleft

The chain corresponding to (51), constructed in the proof of
Theorem G\null, is
$$1, 2, 3, 6, 12, 15, 30, 31, 60, 120, 240, 255, 510, 1020,
1023, 2040,
$$4080, 4095, 8160, 16320, 32640, 65280, 130560, 261120, 26214ff.
?????????????|newtype W58320---
%folio 598 galley 3 Total loss. (C) Addison-Wesley 1978	-
Computer Programmcng∨cm. 4\quad f).5:98g.n36N,????6}o{\:r EXERCISES
}|qleft
 |qleft |newtype {\bf 1. \xskip} $[{\sl 15}]$ What is the value
of $Z$ when Algorithm A termcnkwzs?
|qleft ↓??↓¬??:5fi{\bf *}??6≡??2[::44\[??/??/??4P??4(M\]::[↓??cpzsuu
}¬m}¬iN¬x vrogram for Algorithm A\null, to calckwate $)FgcN4←πmod
←≥εq??ffvv¬fnicmz∧∧jks \??2n [↓knd x, Nπwhere w$ is the word
suze. Assume thaz XKI¬¬fhqushhysx¬ckj¬ymvqjjwpvmfs C¬sC¬lB,
JAE, etc., which aresdescribed in SSktionn|newtype W58320---Computer
Programming\quad ch.
%folio 600 galley 4 Total loss. (C) Addison-Wesley 1978	-
4\quad f. 600\quad g. 4C

\exno 28. [M30] (A. Sch\"onhage.)\xskip
The object of this exercise is to give a fairly short
proof that $l(n) ≥ λ(n) +$ lg $\nu (n) - O($log log??1$\nu (n)
+ 1)??2$.\xskip (a) When $x = (x↓k \ldotsm x↓0, x↓{-1} . . .)↓2$ and
$y = (y↓k \ldotsm y↓0, y↓{-1} . . .)↓2$ are real numbers written
in binary notation, let us write $x \subset y$ if $x↓j ≤ y↓j$
for all $j$. Give a simple rule for constructing the smallest
number $z$ with the property that $x↑\prime \subset x$ and $y↑\prime
\subset y$ implies $x↑\prime + y↑\prime \subset z$. Denoting
this number by $x 6y$, prove that $\nu (x 6y) ≤ \nu (x) + \nu
(y)$.\xskip (b) Given any addition chain (11) with $r = l(n)$, let
$d↓0, d↓1, \ldotss$, $d↓r$ be defined as in (37), andfdefine the
sequence $A↓0, A↓1, \ldotss$, $A↓r$ by the following rules: $A↓0
= 1$; if $a↓i = 2a↓{i-1}$ then $A↓i = 2A↓{i-1}$; if $a↓i = a↓j
+ a↓k$ for some $0 ≤ k < j < i$, then $A↓i = A↓{i-1} 6A↓{i-1}/2↑{d↓j-d↓k}$.
Prove that this sequence ``covers'' the given chain, in the
sense that $a↓i \subset A↓i$ for $0 ≤ i ≤ r$.\xskip (c) Let $\delta$
be a positive integer (to be selected later). Cjll the nondoubling
step $a↓i = a↓j + a↓k$ a ``baby step'' if $d↓j - d↓k ≥ \delta
$, otherwise call it a ``close step.'' Let $B↓0 = 1; B↓i = 2B↓{i-1}$
if $a↓i = 2a↓{i-1}; B↓i = B↓{i-1} 6B↓{i-1}/2↑{d↓j-d↓k}$ fflf
$a↓i ????44fiSβj +]4fiUβkn$/usasxj∧xsszep; afd $BNβi ????44←≤fl(↑↓Fβi↓{?1}))$"ohej∧uue↔,qqyjjs$??/??2≤))↔??7ushhyspwauy
nk¬xbjc}≥y??)ukvhhhqwh}??2??266V∧S44??4(Y4\y??(xgc \??5→44}¬S4??/s44}¬SI4}≤x.
NπSmow that A↓i \subset B↓i$ and $\nu (B↓i)←4≤ (1 + \Delta kNβi)2↑∧XCci$↔brc→→44¬}S44\≥I44}}S46/,??↓qyjjs}≤XIii
[↓kff \??2cIii??3jsqqkvpv¬aqyndfnote the number of baby steps
and close steps \rslash S4$i.,[[int{\sl \!\?$??4ym∧uthuwhhhss53↔sicn}↓XIii??↓qpqajcicncvmfskkuhcvsx∧gmcksnof
size ≥$1 + \delta c↓i.]$\xskip (d) We now have $l(n) ??& r ????44??2XirC4~↓4/CβrC4??????4≡FIrc??$
%folio 604 galley 5 Total loss. (C) Addison-Wesley 1978	-
↓kff|newtype W58320---Computer Programming\quad ch. 4\quad f.
604\quad g. 5C

|qleft \6skip \quad \xskip Several generalizations of Horner's
rule have been suggested. Let us first consider evaluating $u(z)$
when $z$ is a complex number, while the coefficients $u↓k$ are
real. Complex addition and multiplication can obviously be reduced
to a sequence of ordinary operations on real numbers:
$$
|qctr ⊗real + complex⊗requires⊗1 addition\cr
⊗complex + comvlexFLrjqqirdsSL2/addctiomf??/⊗real \times /omvlexFLrjquirdsSL2λmkwliplicationf\cr
⊗comvlexN4\varphi N4comvlex⊗rdquires⊗4fflmkwliplicjwions,n2,additionf\cr
fl⊗⊗or⊗3 mkltiplications,n5 additions\cr
\6skip (See exerccses41.,Su¬bgjkvivnniushsjjscvnfukdjjdfuusikfiphqwjjssqquv∧wwfmhhomujdkhpvm.)nThyjjfbrdsHmrnejfl↔sckqes(??2↔uussssuphyjc$4/N4≤↓N42n$.kqlppppckwpvmf
ufdn$3nN4??≠ 2$,≤jdctpvnfsmgc??↓---N4??????45ffi??[¬qlipppckwpvmfsukff}6N4↓≤455
[↓jdkppcons om fvaluate $u(z)$ when $z = x + iy$ is complex.
An alternative procddkjdsfbr e¬jwuawicvc??ff)X4??44q))??7ushompwzh]≤??????}\ε$a↓1
= u↓n,\qquad b↓1 = u↓{n-}!β1,\qquad r = xS4+ x,\qquad s =←4x↑264↓ffi↓!4≥Sv2)!;????/}a↓j????????????
I444444444444444444444444444444444444444444444444444444444$
%folio 609 galley 6 Total loss (C) Addison-Wesley 1978	-
44444444?????????|newtype W58320---Computer Programming\quad
ch. 4\quad f. 609\quad g. 5C

\subsectionbegin{Adaptation of coefficients} Let us now return
to our original problem of evaluating a given polynomial $u(x)$
as rapidly as possible, for ``random'' values of $x$. The importance
of this problem is due partly to the fact that standard functions
such as sin $x$, cos $x, e↑x$, etc., are usually computed by
subroutines that rely on the evaluation of certain polynomials;
these polynomials are evaluated so often, it is desirable to
find the fastest possible way to do the computation.

Arbitrary polynomials of degree five and higher can be evaluated
with fewer operations than Horner's rule requires, if we first
``adapt'' the coefficients $u↓0, u↓1, \ldotss$, $u↓n$. Such an
adaptation process might involve a fairly complex calculation,
as explained below; but the preliminary calculation is not wasted,
since it must be done only once while the polynomial will be
evaluated many times. For examples of ``adapted'' polynomials
for standard functions, see V. Ya. Pan, {\sl USSR Computational
Math.\ and Math.\ Physics \bf 2} (1963), 137--146.

The simplest case for which adaptation of coefficients is helpful
occurs for a fourth degree polynomial:
$$$u(x) = u↓4x↑4 + u↓3x↑3 + u↓2x↑2 + u↓1x + u↓0,\qquad u↓4 ≠
0.\eqno (8)$
|qctr \6skip This equation can be rewritten in a form suggested
by Motzkin,
$$$y = fl() + ←≤fiSβ0)) ??????4fl??Ui1---`\quad u))??44????444≥\()Y4~↓4??2F4??N4??Ui2)x
????44αSβ3)??Ui4,\eqno (??←;\**Fπ'fbrcsuutab∧yy``jdjpted-',cod∃≡cents |ε*3≤j|β0, |≤_Sβ1, |≤_|β2,λ|≤≠Sβ3,λ|≤≠Sβ4#,|ππhescomvutazionnicnthissfbgvmmbvcokuwy invogves three multiplications, _ve additions, and one instruction to store the partial result |εy |πinoontexviszorjg∧;?bx comvujcsxnntonHorndj⊃↔srkwa↔,washq¬kshgjjddfuumkqlipppckwivmnfxrcaknujdkppvmnukffuusyorccv..Svdfnthpsscomvurjzivdwyssmallisa¬ingksisswbrghhqqipasiffhhyspvgqxmmvuwiiushomxbss¬¬wquwzdfmxxzf..((xfcv¬kks↔,ikfhhyshpvxsfxgcm¬qlppppckwpvmniuscvmvqjj∧∧ws omhhys pcxsnfor jdkitcon, (α) gives no improvement; we will see that a general fourth-degree polyfomcawiuwwaqsscjquucjssuw pwauyhsuvvhhujcphmxzpccmvqjjwpvmfsicnipyss¬¬wquwpvm.))]'!|9|4|1|1|1By comparing coe∃cients in (8) and (9), we obtain formkwassfbr cvmvuqicgchhys|≥*/*2≤UIj≠][(sicnhzjvxsmxfhhys \≥u|rk,N(s:N'{J6skip
??Sβ0 4←f↓5F↓36((UIβff7≡uIffl44↓≠I47),\quad ??≤b = u↓2/u↓4 -
α↓0(α↓0 + 1)↔$\quad α↓1←4=←4ffSβ1/ffSβ4←4??44≤≠Uβ1←??2~↔N;????/¬??I26444V≤x4↓≤I62α↓1,\qquad
α↓3 = u↓0/u↓4 - ←≤a↓1(α↓1 + α↓2),\qquad α↓4←4=←4u↓4---]JD(10)??4:↓J????}[πUsuvvpwa??1c
kvyxx↔,qqpcch ¬¬apuates a fourth-degree i pippppppppppppp??2a↓2←4↓ff↓
←≤~ -??442α↓1,\qquad \xi ↓3 ?? ffUi0/k↓444≤↓N4\xi ↓1(N≤a↓1 +
α↓2),\qquad α↓4 = u↓4.\eqno (10)$
|qctr \6skip A similar scheme, which evaluates a fourth-degree
pogqxomialhin the same number of steps as (9), appears in exercise
18; this alternative method will give greater numerical accuracy
than (9) in certain cases, although it yields poorer accuracy
in other cases.

Polynomials that arise in practice often have a rather small
leading coefficient, so that the division by $u↓4$ in (10) leads
to instability. In such a case it is usually preferable to replace
$x$ by $|u↓4| ↑{1/4}x$ as the first step/,reducing (8) to \pm
a monic polynomial. A similar transformation applies to polyxmmvulysoffhigmejndd∧rdes),Thissidda
issfkesto C---,T. Fikes$[6ACMn${\bf 1}←≡??(1967)↔,175--378],,wyo
hassprdsentedfseverjl inoerdstingnexamples.

Anx polynomial of the fifth degree may be evaluated using four
multiplications, six additions, and one storing, by using the
rule $u(x) = U(x)x + u↓0$, where $U(x) = u↓5x↑4 + u↓4x↑3 + u↓3x↑2
+ u↓2x + u↓1$ is evaluated as in (9). Alternatively, we can
do the evaluation with four multiplications, five additions,
and three storings, ifsthe calculations take the form??'\6skip
$????????????|newtype$ W58320---Computer
%folio 611 galley 7 Mostly wiped out. (C) Addison-Wesley 1978	-
Programming\quad ch. 4\quad f. 611\quad g. 7C

|qleft \6skip \quad \xskip Another method for doing sixth-degree
equations has been suggested by V. Ya. Pan [see L. A. Lyusternik,
O. A. Chervonenkis, A. R. Yanpol'skii, {\sl Handbook for Computing
Elementary Functions}, tr. by G. J. Tee (Oxford: Pergamon, 1965),
10--16]. Pan's method requires one more addition operation,
but it does not involve first solving a cubic equation in the
preliminary steps. We may proceed as follows:
$$$z = (x + α↓0)x + α↓1,\qquad w = z + x + α↓2$,
|qctr \4skip u(x) = ??1((z - x + α$↓3)w + α↓4)z + α↓5??2α↓6.\eqno
(16)$
|qctr \6skip To determine the $α$'s, once again divide the polynomial
by $u↓6 = α↓6$ so that $u(x)$ becomes monic. It can then be
verified thaw $α↓0 = u↓5/3$ and that
$$$α↓1 = (u↓1 - α↓0u↓2 + α|spose ↓0↑2u↓3 - α|spose ↓0↑3u↓4 +
2α|spose ↓0↑5)/(u↓3 - 2??ote that Pan's method requires that
the denominator does not vanish; i.e$.,
$$$27u↓3u|spose ↓6↑2 - 18u↓6u↓5u↓4 + 5u|spose ↓5↑3 ≠ 0;\eqno
(18)$
|qctr \6skip in fact, this quantity should not be so small that
$α↓1$ becomes too large. Once $α↓1$ has been determined, the
remaining $α$'s may be determined from the equations
$$$β↓1 = 2α↓0,\qquad β↓2 = u↓4 - α↓0β↓1 - α↓1,\qquad β↓3 = u↓3
- α↓0β↓2 - α↓1β↓1$,
|qctr \4skip β$↓4 = u↓2 - α↓0β↓3 - α↓1β↓2$,
|qctr \4skip α$↓3 = {1\over 2}??1β↓3 - (α↓0 - 1)β↓2 + (α↓0 -
1)(α|spose ↓0↑2 - 1)??2 - α↓1$,
|qctr \4skip α$↓2 = β↓2 - (α|spose ↓0↑2 - 1) - α↓3 - 2α↓1,\qquad
α↓4 = β↓4 - (α↓2 + α↓1)(α↓3 + α↓1)$,
|qctr \4skip α$↓5 = u↓0 - α↓1β↓4.\eqno (19)$
|qctr \6skip \quad \xskip We have discussed the cases of degree
$n = 4, 5, 6$ in detail because the smaller values of $n$ arise
most frequently in applications. Let us now consider a general
evaluation schemd fxrc$)Nπ"hhfd∧gjespvgqfmmcuwq↔,qqpcvhuwwwqyshakkss??\.ffv/66.3P4~↓466??.¬qlppppckwpvmfsukff}??2n
Nπjdkipcmnf.N'N'\bf The}???a general evaluation scheme for $n$th
degree polynomials, which always takes $\lfloor n/2\rfloor +
2$ multiplications and $n$ addutions.N'

\thbegin Theorem E. {\sl Every $n$th degree polynomial
$(1)$ with real coefficients, $n ≥ 3$, can be evaluated by
the scheme}
$$$y = x + c,\qquad w = y↑2$;
|qctr \4skip z = (u$↓ny + α↓0)y + β↓0\quad (n$ even),\qquad
$z = u↓ny + β↓0\quad (n$ odd);
|qctr \4skip $q(x) = ??1\cdot \cdot \cdot N4((z(w - α↓1)N4??N4β↓1)(w
- α↓2) ?? β↓2) \cdot \cdot \cdot ??2(w - α↓m) + β↓m;\eqno (20)$
|qctr \6skip {\sl for suutabwe real paramezers c, α↓k and βSβk,
whejd m = \lfloor n/2\rfloor - 1. In fact it is possible to
select these paramezersssbnthaw ??&??FimN4??????45.],]]'??\roof)]9!44[3az
uusff≠ky sx¬¬vcfshhyscccck¬xywkckssukfdjr whcch the N≤a'}s and
$β$'s cak be chmfen in (20), ikf$c ??/usfi)dd(:paz??↓??????}\εp())4??24??/??2(X4↓≤46??2)4??24??/uIcnxCgn
+ a↓np(x)??44=←4ff) ??←4/)←4= a↓nx↑n ?? aSβcNi↓≠↓i1)↑nNv????4g344+
\cdot N4\cdot ←¬O + a↓1x + a↓0.\eqno (21)$
|qctr \6skip We want to show that $p(x)$ has the form $p↓1(x)(x↑2
- α↓m) + β↓m$ for some polynomial $p↓1(x)$ and some constants
$α↓m, β↓m$. If we divide $p(x)$ by $x↑2 - α↓m$, we can see that
the remainder $β↓m$ is a constant only if the auxiliary polynomial
$$$q(x) = a↓{2m?1}x↑m + a↓{2m-1})↑{m-}Ng3 + \cdots
+ a↓1,\eqno (22)$
|qctr \6skip formed from every odd-numbered coefficient of $p()),$,is
a muwtpple of $x - α↓m$. Convdrfely, if $q(x)λ$has $x ????44←≤≠Sβm$
≠usasfjkvog/,hhsfn??≥))(4??2(4ffiPi1))()XV364≤↓44≤UIv)(4??44≤XIv.,??(xgcsxmxscvmfywkmh
U≥????≤xIcm, N3qhcch may be determined by division.
|qleft \quad \xskip 4541??/uvcpwjgq),qwsqwkmh}≥pIfi()) [πomhq¬¬s
hhsnform $p↓2(x)(x↑2 - α↓{m-1}) + βFβm↓-←β1,$,≠fdfthiusiushhyssu¬xsuussuqqcvvhhqwh??≥()??2(X4↓↓44≤auIv))
[7usuunvultiple of $x - α↓{m-1}$; for if $q↓1())$ is thespolynomcuwpcgrrjsqvmfkcvvhom}≥pIfi())
[↓us \≥¬(x) M7corresponds to $p(x)$, we have ??≥$↓1(x) = q(x)/(x
- α↓m). ??7vmminkucvvicnhhessu¬xsqwq),qwsff≡ffhhqwhhhyspqjj¬xzzjks
\≥≤uIβ3, N≤??1bIβ3, \ldotss$, $α↓m$, $β↓m$ willisxist if and only
if
$$$q()(44??/UI26IvMI↓??I1(x4????↓≠I4C≤u↓3) N¬O \ldotsm (x
- α↓m).\eqno (23)$
|qctr \6skip ICnmohyjcq∧gjff, uphyjc??≥??2())??7us|tab either\qquad
|tab $λ↓i = (\pm λ↓j) ?? λ↓k,\qquad |tab 0 ≤ j, k < i⊗\4skip
⊗⊗λ↓i = α↓j ?? λ↓k,⊗0 ≤ k < i.\eqno (25)\cr
\6skip$ Here ``??'' denotes any of the three operations ``+'',
``-'', or ``\times'', and $α↓j$ denotes a so-called ``parameter.''
Steps of the first kind are called {\sl chain steps}, and steps
of the second kind are called {\sl parameter steps.} We shall
assume that a different parameter $α↓j$ is used in each parameter
step; if there are {\sl s parameter steps, they should involve}
$α↓1$, $α↓2$, $\ldotss$, $α↓s$ in this order.

It follows that the polynomial $u(x)$ at the end of the chain
has the form
$$$u(x) = q↓nx↑n + \cdots + q↓1x + q↓0,\eqno (26)$
|qctr \6skip where $q↓n, \ldotss$, $q↓1$, $q↓0$ are polynomials
in $α↓1, α↓2, \ldotss$, $α↓s$ with integer coefficients. We shall
interpret the parameters $α↓1, α↓2, \ldotss$, $α↓s$ as real numbers,
and we shall therefore restrict ourselves to considering the
evaluation of polynomials with real coefficients. The {\sl result
set R} of a polynomial chain is defined to be the set of all
vectors $(q↓n, \ldotss$, $q↓1$, $q↓0)$ of real numbers that occur
as $α↓1, α↓2, \ldotss$, $α↓s$ independently assume all possible
real values.

If fbr everyscmoicdsof $ffi +N41$ dcszinco inoe∧ers $j↓0, .]4.
.←4, j↓t \in \{0, 1, \ldotss, n\}$ there is a nonzero multivariate
polynomial $f$ ≤qphhicmz∧brncvbffi??2cefoyssukv thuw $f(??2Sβj|infinf
π, . .N4.←4,]4q↓j|infinf t) = 0λ$for all $(q↓n,N4. . .←4, q↓1,
q↓0)$ in $R$, let us say that the result set $R$ has at most
$ffl$ Nε-d∧rdessmfffkjedbm,,??≠kdfhhqwhhhescvqucn(6))hqusat
mofz $ffl$ ddgrdessofffrdedom.λWe also say thaz the chain (24),{\sl
computes} a given polynomial $u(x) = uSβnx↑n + ??N44¬O ←¬B ??!4ffSβ1)S4+??44ffSβ0λ??7kf(u↓n,
.]4. .]4, u↓1/,u↓0)↔$ffls in $R$. It follows that a polynomial
chain with at most $≡n$-d∧rjessofffkjedbmmcjknmohcmmvuqzsawl
$nNπ"hhdd∧rde polyfomiawss(seesexerccues27).←''\quad ??Y4As
an examplesof a polynomial chain,,consider the followingncmwin
correspondcng to TheorexnE, when nn$cs odd:!'↓A6}$&$
|qctr \hfill λ$↓0 ⊗= x\cr
\2skip \hfill λ↓1 ⊗= α↓1 +N4λ↓0\cr
\2skip \hfill λ↓2 ⊗= λ↓1 \times λ↓1\cr
\2skip \hfill λ↓3 ⊗= α↓2 \times λ↓1\cr
\2skip \hfill λ↓{1+3i} ⊗= α↓{1+2i} + λ↓{3i}\cr
\2skip \hfill λ↓{2+3i} ⊗= α↓{2+2i} + λ↓2\cr
\2skip \hfill λ↓{3?}fl↓3←βiI4←P??24←≤g↓14β↓ffi↓????β3]βi \Delta
??44←≤≤Iβ26β??iβ3↓i\cr
|raiseordrop$ "Theresare $!"fin/2]"1 ??????42λ$.kqtippickwivnfsukff}??2n??≤jdkppvmf;$;|raise2
ffv/66.3P4~↓N41λ??/vwinnszeqssafffn + 1$ parameter steps),By
Theorem E\null, the result set $R$ includes the set of all $(u↓n,
\ldotss , u↓1, u↓0)$ with $u↓nN44ff!↔6??]41;$;so (27) computes
all polynomials of degree $n.λ$We cannot prove that $R$ hassaz
moft $n$ -d∧gjessofffrdedom,,succdsthescjsuwthssz huus$↔N4~↓??441λ$/nfdqaffdfo
comvonffmy)]''\quad !4$% polynomial chain with s paraxeter szeqs
hausaz mmxyhssde∧rjessofffkjedbm..??6nnaussffsshhpusiusmb¬vv¬u:?ckk,"
cvmvuqesuufkkcvivnnqqph ε ????∧gjessmfffkjedbmmqqphhpwssshhqkn}εh??↓j∧¬pgjj¬ypqjj¬xezjkf.f}uh
dvdn this intuitive fact is not easy to prove formally; for
example, there are continuous fkkctions (``space-filling ckjvjs↔'))qyicm
mkqithescjawpppcfsmmmomuuppwkf↔,ukffqqpcvhhhyjjfxgjsn¬qpuu scngle
pjrkmetdr into two independent parameters. For our purposes↔,we
ndedftonvejckxyhhuwhnmmpvgqfmmcuwpfkkcvpgnfsqqph icme∧∧jccvbffi??2cufmysckknhq¬¬ss|newtype$
%folio 614 galley 8 Tape worthless. (C) Addison-Wesley 1978	-
\algbegin Theorem M (\rm T. S. Motzkin, 1954). 
{\sl A polynomial chain with $m > 0$ multiplications has at most
$2m$ degrees of freedom.}

\proofbegin Let $\mu ↓1$, $\mu ↓2$, $\ldotss$, $\mu ↓m$ be
the $λ↓i$'s of the chain that correspond to multiplication
operations. Then
$$\baselineskip15pt
\eqalignno{\mu ↓i⊗= S↓{2i-1}\times S↓{2i},\qquad 1 ≤ i ≤ m,\cr
u(x) ⊗= S↓{2m+1},⊗(28)\cr}$$
where each S↓j$ is a certain sum of $\mu$'s, $x$'s, and $α$'s. Write
$S↓j = T↓j + β↓j$, where $T↓j$ is a sum of $\mu$'s and $x$'s while $β↓j$ is a sum
of $α$'s.

Now $u(x)$ is expressible as a polynomial in $x$, $β↓1$, $\ldotss$, $β↓{2m+1}$ with
integer coefficients. Since the $β$'s are expressible as linear functions of
$α↓1$, $\ldotss$, $α↓s$, the set of values represented by all real values of
$β↓1$, $\ldotss$, $β↓{2m+1}$ contains the result set of the chain. Therefore there
are a most $2m+1$ degrees of freedom; this can be improved to $2m$ when $m>0$, as
shown in exercise 30.\quad\blackslug

\yyskip An example of the construction in the proof of Theorem M appears in
exercise\penalty999\ 25. A similar result can be proved for additions:

\algbegin Theorem A (\rm\'E. G. Belaga, 1958). {\sl A polynomial chain containing
$q$ additions and subtractions has at most $q+1$ degrees of freedom.}

\proofbegin [{\sl Problemi Kibernetiki \bf5} (1961), 7--15.]\xskip Let $\kappa↓1$,
$\ldotss$, $\kappa↓q$ be the $λ↓i$'s of the chain that correspond to addition or
subtraction operations. Then
$$\baselineskip15pt
\eqalignno{\kappa↓i⊗=\pm T↓{2i-1}\pm T↓{2i},\qquad 1 ≤ i ≤ q,\cr
u(x)⊗=T↓{2q+1},⊗(29)\cr}$$
where each $T↓j$ is a product of $\kappa$'s, $x$'s, and $α$'s. We may write
$T↓j=A↓jB↓j$, where $A↓j$ is a product of $α$'s and $B↓j$ is a product of $\kappa$'s
and $x$'s. The following transformation may now be made to the chain, successively
for $i=1$, 2, $\ldotss$, $q$:\penalty-100\ Let $β↓i=A↓{2i}/A↓{2i-1}$, so that
$\kappa↓i=A↓{2i-1}(\pm B↓{2i-1}\pm β↓iB↓{2i})$. Then change $\kappa↓i$ to
$\pm B↓{2i-1}\pm β↓iB↓{2i}$, and replace each occurrence of $\kappa↓i$ in future
formulas $T↓{2i+1}$, $T↓{2i+2}$, $\ldotss$, $T↓{2q+1}$ by $A↓{2i-1\kappa↓i}$.\xskip
(This replacement may change the values of $A↓{2i+1}$, $A↓{2i+2}$, $\ldotss$,
$A↓{2q+1}$.)

After the above transformation has been done for all $i$, let $β↓{q+1}=A↓{2q+1}$;
then $u(x)$ can be expressed as a polynomial in $β↓1$, $\ldotss$, $β↓{q+1}$, and
$x$, with integer coefficients. We are almost ready to complete the proof, but
it is necessary to be careful because the values representable by this polynomial
in $β↓1$, $\ldotss$, $β↓{q+1}$ may not include all values obtainable by the
original chain (see exercise 26); it is possible to have $A↓{2i-1}=0$, for some
values of the $α$'s, and this makes $β↓i$ undefined.

To complete the proof, let us observe that the result set $R$ of the original chain
can be written $R=R↓1∪R↓2∪\cdots∪R↓q∪R↑\prime$, where $R↓i$ is the set of result
vectors possible when $A↓{2i-1}=0$, and $R↑\prime$ is the set of result vectors
possible when all $α$'s are nonzero. The discussion above proves that $R↑\prime$
has at most $q+1$ degrees of freedom. If $A↓{2i-1}=0$, then $T↓{2i-1}=0$, so
addition step $\kappa↓i$ may be dropped to obtain another chain computing the
result set $R↓i$; by induction we see that each $R↓i$ has at most $q$ degrees
of freedom. Hence by exercise 29, $R$ has at most $q+1$ degrees of freedom.\quad
\blackslug

\thbegin Theorem C. {\sl If a polynomial chain computes all $n$th degree polynomials
$u(x)=u↓nx↑n+\cdots+u↓0$, $u↓n≠0$, for some $n≥2$, then it includes at least
$\lfloor n/2\rfloor+1$ multiplications and at least $n$ addition-subtractions.}

\proofbegin Let there be $m$ multiplication steps. By Theorem M\null, the chain has
at most $2m$ degrees of freedom, so $2m≥n+1$. Similarly, by Theorem A there are
$≥n$ addition-subtractions.\quad\blackslug

\yyskip This theorem states that no {\sl single} method having fewer than $\lfloor
n/2\rfloor+1$ multiplications or fewer than $n$ additions can evaluate all possible
$n$th degree polynomials. The result of exercise 29 allows us to strengthen this
and say that no finite collection of such polynomial chains will suffice for all
polynomials of a given degree. Some special polynomials can, of course,
be evaluated more efficiently: all we have really proved is that polynomials whose
coefficients are {\sl algebraically independent}, in the sense that they satisfy
no nontrivial polynomial equation, require $\lfloor n/2\rfloor+1$ multiplications
and $n$ additions. Unfortunately the coefficients we deal with in computers are
always rational numbers, so the above theorems don't really apply; in fact, we can
always get by with $O(\sqrt n\,)$ multiplications (and a possibly huge number of
additions), as shown in exercise 42. From a practical standpoint, the bounds of
Theorem C apply to ``almost all'' coefficients, and they seem to apply to all
reasonable schemes for evaluation. Furthermore it is possible to obtain lower
bounds corresponding to those of Theorem C even in the rational case: By
strengthening the above proofs, V. Strassen has shown, for example, that the
polynomial
$$\chop to 12pt{u(x)=\sum↓{0≤k≤n}2↑{2↑{kn↑3}}x↑k}\eqno(30)$$
cannot be evaluated by any polynomial chain of length $<n↑2/\!\lg n$ unless the
chain has at least ${1\over2}n-2$ and $n-4$ additions [{\sl SIAM J. Computing
\bf3} (1974), 128--149].  The coefficients of (30) are very large; but it is
also possible to find polynomials whose coefficients are just 0's and 1's, such
that every polynomial chain computing them involves at least $\sqrt n/(4\lg n)$
chain multiplications, for all sufficiently large $n$, even when the parameters
$α↓j$ are allowed to be arbitrary complex numbers.\xskip[See R. J. Lipton,
{\sl SIAM J. Computing \bf7} (1978), 61--69; C. P. Schnorr, {\sl Lecture Notes
in Comp.\ Sci.\ \bf53} (1977), 135--147.]

A gap still remains between the lower bounds of Theorem C and the actual operation
counts known to be achievable, except in the trivial case $n=2$. Theorem E gives
$\lfloor n/2\rfloor+2$ multiplications, not $\lfloor n/2+1$, although it does
achieve the minimum number of additions. Our special methods for $n=4$ and $n=6$
have the minimum number of multiplications, but one extra addition. When $n$ is
odd, it is not difficult to prove that the lower bounds of Theorem C cannot
be achieved simultaneously for both multiplications and additons; see exercise
33. For $n=3$, 5, and 7, it is possible to show that at least $\lfloor n/2\rfloor
+2$ multiplications are necessary. Exercises 35 and 36 show that the lower bounds
of Theorem C cannot both be achieved when $n=4$ or $n=6$; thus the methods we have
discussed are best possible, for $n<8$. When $n$ is even, Motzkin proved that
$\lfloor n/2\rfloor+1$ multiplications are sufficient, but his construction
involves an indeterminate number of additions (see exercise 39). An optimal scheme
for $n=8$ was found by V. J. Pan, who showed that $n+1$ additions are necessary
and sufficient for this case when there are $\lfloor n/2\rfloor+1$ multiplications;
he also showed that $\lfloor n/2\rfloor+1$ multiplications and $n+2$ will suffice
for all even $n≥10$. Pan's paper [{\sl Proc.\ ACM Symp. Theory of Computing \bf10}
(1978), 162--172] also establishes the exact minimum number of multiplications
and additions needed when calculations are done entirely with complex numbers
instead of reals, for all degrees $n$. Exercise 40 discusses the interesting
situation that arises for odd values of $n≥9$.
%folio 618 galley 9 Unreadable. (C) Addison-Wesley 1978	-
Programming\quad ch. 4\quad f. 618\quad g. 9C

|qleft \6skip \quad \xskip It is clear that the results we have
obtained about chains for polynomials in a single variable can
be extended without difficulty to multivariate polynomials.
For example, if we want to find an optimum scmeme for polynomial
evaluation {\sl without} adaptation of coefficients, we can
regard $u(x)$ as a polynomial in the $n + 2$ vjriables $x, u↓n,
\ldotss$, $u↓1$, $u↓0$; exercise 38 shows that $n$ multiplications
and $n$ additions are necessary in this case. Indeed, A. Borodcn
[{\sl Theory of Machines and Computations}, ed.\ by Z. Kohavi
and A. Paz (]dw York: Academic Press, 1971), 45--58] has proved
that Homer's rule (2) is essentially the {\sl only} way to compute
$u(x)$ in $2n$ operations without preconditioning.

With minor variations, the above methods cjknxbssxxzffddfhomcmaunf
invogvcng dcvision, i.e., to rational functions as well as polynomials.
Curiously, the continued-fraction analog of Homer's rule now
turns out to be optimal from an operation-≡ouft stafdvocno,nif
mkqtiplicjzion andndivision speed aje equal, even when preconditioning
is allowed (seesexercise 37).]'??1\quad \xskip ←1!bmetimes division
is hzlpfkwifkkccgnthesevjluationnoffpogynomcaws, evdfnthougm
pvgyxomcuwqsujdsfdfi≡fdfmmvqyicnhzjvxsmxfmkwlppppckwpvmnukffujdkppvm);qwshq¬¬sssefnsx¬¬vpwssmmfhhpisicn
the Shaw--Trakb algorithms for polynomial derivazives. Akothercsx¬¬vlwsiushhyspvgqxmmvuwp}??2XVvN4??44}}M44}¬M44}¬MI6??I6x
?? 1: Since it can be written$ ()Fgn↑+!g1 -!41)/(xF4↓≠↓ 1)↔λ$we
can evjwuazesip inn {\sl lllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllllll??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad ??\quad
??\quad ??\quad}